<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
  <head>
    <meta charset="utf-8" />
    <meta name="generator" content="pandoc" />
    <meta
      name="viewport"
      content="width=device-width, initial-scale=1.0, user-scalable=yes"
    />
    <title>README</title>
    <style type="text/css">
      code {
        white-space: pre-wrap;
      }
      span.smallcaps {
        font-variant: small-caps;
      }
      span.underline {
        text-decoration: underline;
      }
      div.column {
        display: inline-block;
        vertical-align: top;
        width: 50%;
      }
    </style>
  </head>
  <body>
    <h1 id="tree">Tree</h1>
    <p>
      A <strong>tree</strong> is a non-linear data structure that simulates a
      hierarchical tree structure.
    </p>
    <ul>
      <li><a href="#general-tree">General Tree</a></li>
      <li><a href="binary-tree">Binary Tree</a></li>
      <li><a href="binary-search-tree">Binary Search Tree</a></li>
      <li><a href="../../algorithms/tree">Traversal</a></li>
      <li><a href="#terminology">Terminology</a></li>
    </ul>
    <h2 id="general-tree">General Tree</h2>
    <p><img src="../../../assets/k-ary_tree.svg" width="600" /></p>
    <p>
      A <strong>general tree</strong>, or <em>k</em>-ary tree, is made up of
      <strong>nodes</strong> (or <strong>vertices</strong>) connected by
      <strong>edges</strong>.
    </p>
    <p>
      A tree has a <strong>root</strong> node and potentially many
      <strong>levels</strong> of an arbitrary number of
      <strong>children</strong> that form a hierarchy.
    </p>
    <p>
      If a node is connected to other nodes below it, that node is called the
      <strong>parent</strong> node, and the nodes following it are called
      <strong>child</strong> nodes. Each node in the tree can be see as a
      <strong>subtree</strong>.
    </p>
    <h2 id="constraints">Constraints</h2>
    <ul>
      <li>
        A child has only <em>one</em> parent and the root node has
        <em>no</em> parent.
      </li>
    </ul>
    <p><em>Note: A tree is a graph without cycles.</em></p>
    <h2 id="common-operations">Common Operations</h2>
    <h4 id="insert">Insert</h4>
    <p>Inserts a node in the tree.</p>
    <h4 id="search">Search</h4>
    <p>
      This searches for a node with the given value in the tree and returns
      <code>true</code> if it exists, otherwise <code>false</code>.
    </p>
    <h4 id="minmax">Min/Max</h4>
    <p>Returns the minimum or maximum value in the tree.</p>
    <h4 id="remove">Remove</h4>
    <p>Removes a node from the tree.</p>
    <h2 id="terminology">Terminology</h2>
    <h4 id="root">Root</h4>
    <p>The top node in a tree.</p>
    <h4 id="child">Child</h4>
    <p>
      A node directly connected to another node when moving away from the root.
    </p>
    <h4 id="parent">Parent</h4>
    <p>A node with other nodes connected below it.</p>
    <h4 id="siblings">Siblings</h4>
    <p>A group of nodes with the same parent.</p>
    <h4 id="leaf">Leaf</h4>
    <p>A node with no children.</p>
    <h4 id="branch-node">Branch node</h4>
    <p>A node with at last one child.</p>
    <h4 id="degree">Degree</h4>
    <p>
      For a given node, its number of children. A leaf is necessarily degree
      zero.
    </p>
    <h4 id="edge">Edge</h4>
    <p>The connection between one node and another.</p>
    <h4 id="path">Path</h4>
    <p>A sequence of nodes and edges connecting a node with a descendant.</p>
    <h4 id="level">Level</h4>
    <p>
      The level of a node is defined as: 1 + the number of edges between the
      node and the root.
    </p>
    <h4 id="depth">Depth</h4>
    <p>
      The depth of a node is defined as: the number of edges between the node
      and the root.
    </p>
    <h4 id="height-of-node">Height of node</h4>
    <p>
      The height of a node is the number of edges on the longest path between
      that node and a leaf.
    </p>
    <h4 id="height-of-a-tree">Height of a tree</h4>
    <p>The height of a tree is the height of its root node.</p>
    <h4 id="forest">Forest</h4>
    <p>A forest is a set of <code>n ≥ 0</code> disjoint trees.</p>
    <hr />
    <h4 id="references"><em>References</em></h4>
    <p>
      _<a href="https://en.wikipedia.org/wiki/Tree_(data*structure)"
        >Wikipedia — Tree (data structure)</a
      >*
    </p>
    <p><a href="#tree">↑</a></p>
  </body>
</html>
